/**
 * https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
 * 两数之和
 * @param root 
 * @param k 
 */
const findTarget = (root: TreeNode | null, k: number): boolean => {
    // 树为空, 直接返回false
    if (root === null) return false

    // 存放升序的数
    const map: Record<number, boolean> = {}

    let ans = false;
    /**
     * 中序遍历
     * @param n 
     */
    const preOrder = (n: TreeNode | null) => {
        if (n === null || ans) return;

        if (map[n.val]) { ans = true; }
        else {
            // 期待的值
            map[k - n.val] = true
        }
        // 遍历左子树
        preOrder(n.left)

        // 遍历右子树
        preOrder(n.right)
    }
    preOrder(root)
    return ans
};


const findTarget2 = (root: TreeNode | null, k: number): boolean => {
    // 树为空, 直接返回false
    if (root === null) return false

    // 存放升序的数
    const nums: number[] = []

    /**
     * 中序遍历
     * @param n 
     */
    const inOrder = (n: TreeNode | null) => {
        if (n === null) return;

        // 遍历左子树
        inOrder(n.left)

        nums.push(n.val)

        // 遍历右子树
        inOrder(n.right)
    }
    inOrder(root)
    // 双指针开始查找
    let e = nums.length - 1;

    // 最大的大于了所要找的, 直接返回false
    // if (nums[e] > k) return false

    while (e > 0) {
        let m = 0;
        while (m < e) {
            // 从前往后
            if (nums[e] + nums[m] === k) return true;
            m++
        }
        // 还是没找到
        e--; // 尾指针向前走, 继续查找
    }
    return false
};